package com.linchong.tree;

import java.util.Stack;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-12-05 18:02
 * @Description: ValidateBinarySearchTree$验证二叉搜索树
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 *
 * 假设一个二叉搜索树具有如下特征：
 *
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * 示例 1:
 *
 * 输入:
 *     2
 *    / \
 *   1   3
 * 输出: true
 * 示例 2:
 *
 * 输入:
 *     5
 *    / \
 *   1   4
 *      / \
 *     3   6
 * 输出: false
 * 解释: 输入为: [5,1,4,null,null,3,6]。
 *      根节点的值为 5 ，但是其右子节点值为 4 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
 *
 * 1.中序遍历
 *
 * 2.递归判断
 *
 */
public class ValidateBinarySearchTree {

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode() {}
		TreeNode(int val) { this.val = val; }
		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	public boolean isValidBST2(TreeNode root){
		return isValidBST2(root,Long.MIN_VALUE,Long.MAX_VALUE);
	}

	public boolean isValidBST2(TreeNode root,long minVal,long maxVal) {
		if (root == null){
			return true;
		}
		if (root.val >= maxVal || root.val <= minVal){
			return false;
		}
		return isValidBST2(root.left, minVal, root.val) && isValidBST2(root.right, root.val, maxVal);
	}
	public boolean isValidBST(TreeNode root) {
		if(root == null){
			return true;
		}
		Stack<TreeNode> stack = new Stack<>();
		TreeNode pre = null;
		while (root!=null||!stack.isEmpty()){
			while (root!=null){
				stack.push(root);
				root = root.left;
			}
			root = stack.pop();
			if(pre!=null && root.val<pre.val){
				return false;
			}
			pre = root;
			root = root.right;
		}
		return true;
	}

}
